package leetcode.array;

/**
 * @author Cheng Jun
 * Description: 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，
 * 它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
 * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2022/1/27 11:25
 */
public class movingCount {
    public static void main(String[] args) {
        System.out.println(movingCount(3, 2, 17));
    }

    // 不知道为什么这题 使用 static变量，在LeetCode提交出错，但是测试是能通过。所以就没用使用 static变量
    // 1 <= n,m <= 100
    // 0 <= k <= 20
    public static int movingCount(int m, int n, int k) {
        boolean[][] used = new boolean[m][n];
        int res = dfs(m, n, k, used, 0, 0);
        return res;
    }

    static int dfs(int m, int n, int k, boolean[][] used, int rowIndex, int colIndex) {
        if (rowIndex < 0 || rowIndex >= m || colIndex < 0 || colIndex >= n ||
                used[rowIndex][colIndex] || getNum(rowIndex) + getNum(colIndex) > k) {
            return 0;
        }
        used[rowIndex][colIndex] = true;
        return 1 +
                dfs(m, n, k, used, rowIndex + 1, colIndex) +
                dfs(m, n, k, used, rowIndex - 1, colIndex) +
                dfs(m, n, k, used, rowIndex, colIndex + 1) +
                dfs(m, n, k, used, rowIndex, colIndex - 1);
    }

    // 数字的位数之和
    static int getNum(int num) {
        int res = 0;
        while (num != 0) {
            res += num % 10;
            num = num / 10;
        }
        return res;
    }
}
